import copy

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        dp=[[int(i) for i in j] for j in matrix]
        h=len(matrix)
        w=len(matrix[0])
        ret=0
        for i in range(h):
            if dp[i][0]:
                ret=1
        for j in range(w):
            if dp[0][j]:
                ret=1
        for i in range(1,h):
            for j in range(1,w):
                if dp[i][j]:
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
                    ret=max(dp[i][j],ret)
        return ret*ret


# 执行用时：
# 80 ms
# , 在所有 Python3 提交中击败了
# 90.44%
# 的用户
# 内存消耗：
# 20.3 MB
# , 在所有 Python3 提交中击败了
# 42.25%
# 的用户